#include <iostream>
#include <queue>

#include "common/utils.hpp"

TreeNode* searchBST(TreeNode* root, int val) {
    if (root == nullptr || val == root->val) return root;

    std::queue<TreeNode*> que;
    que.push(root);

    while(!que.empty()) {
        TreeNode* node = que.front();
        que.pop();

        if (val == node->val) return node;
        else if (val < node->val) {
            if (node->left != nullptr) que.push(node->left);
        } else {
            if (node->right != nullptr) que.push(node->right);
        }
    }

    return nullptr;
}

extern TreeNode* commonRoot;

int main() {
    std::vector<int> nums = { 4, 2, 7, 1, 3 };
    TreeNode* node = createTreeNodeByArray(nums);
    printTreeNode(node);
    std::cout << "=================\n";
    TreeNode* ret = searchBST(node, 2);
    printTreeNode(ret);
}